{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>目录<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#需求\" data-toc-modified-id=\"需求-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>需求</a></span></li><li><span><a href=\"#思想：\" data-toc-modified-id=\"思想：-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>思想：</a></span></li><li><span><a href=\"#实现\" data-toc-modified-id=\"实现-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>实现</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 需求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "最长公共前缀\n",
    "编写一个函数来查找字符串数组中的最长公共前缀。\n",
    "如果不存在公共前缀，返回空字符串 \"\"。\n",
    "示例 1:\n",
    "输入: [\"flower\",\"flow\",\"flight\"]\n",
    "输出: \"fl\"\n",
    "示例 2:\n",
    "输入: [\"dog\",\"racecar\",\"car\"]\n",
    "输出: \"\"\n",
    "解释: 输入不存在公共前缀。\n",
    "说明:\n",
    "所有输入只包含小写字母 a-z 。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 思想：\n",
    "1. 取出所有字符串的第1个字符\n",
    "1. 比较\n",
    "1. 取出所有字符串的第2个字符\n",
    "1. 重复操作\n",
    "1. 直到比较完list中最小长度字符串前的所有字符\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def longestCommonPrefix(strs):\n",
    "    \"\"\"\n",
    "    :type strs: List[str]\n",
    "    :rtype: str\n",
    "    \"\"\"\n",
    "    if len(strs) == 0:\n",
    "        return \"\"\n",
    "    str_index = 0\n",
    "    list_index = 0\n",
    "    end = 0\n",
    "    c = ''\n",
    "    list_len =len(strs)\n",
    "\n",
    "    while list_index < list_len and str_index < len(strs[list_index]):\n",
    "        if list_index == 0:\n",
    "            # 取出任意j字符串否第i个字符\n",
    "            c = strs[list_index][str_index]\n",
    "        else:\n",
    "            if strs[list_index][str_index] != c:\n",
    "                # 值不同，此时j为最大公共字符串的长度\n",
    "                break\n",
    "        # j到达最大值为列表中的字符串比较完毕，索引归零开始比较所有字符串的下一个索引值\n",
    "        if list_index == len(strs) - 1:\n",
    "            str_index += 1\n",
    "            list_index = 0\n",
    "            end += 1\n",
    "        # 列表中的字符串未比较完，比较下一个字符串的值\n",
    "        else:\n",
    "            list_index += 1\n",
    "\n",
    "    return strs[list_index][:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "**********************************tess passed!**********************************\n"
     ]
    }
   ],
   "source": [
    "assert longestCommonPrefix( [\"flower\",\"flow\",\"flight\"]) == \"fl\"\n",
    "assert longestCommonPrefix( [\"flower\",\"flow\",\"floght\"]) == \"flo\"\n",
    "assert longestCommonPrefix( [\"flower\",\"flow\",\"ght\"]) == \"\"\n",
    "assert longestCommonPrefix( [\"flower\",\"flow\"]) == \"flow\"\n",
    "print('tess passed!'.center(80,'*'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "base"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "目录",
   "title_sidebar": "大纲",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
